package com.qch.edu.lagou.strmatch;

/**
 * bad方法没看懂
 *
 * @Author qch
 * @Date 2021/7/21
 * 滑动匹配法
 * 坏字符规则
 * 坏字符：
 * 如果我们拿坏字符，在模式串中顺序遍历查找，这样就会比较低效
 * 可以采用散列表，我们可以用一个256数组，来记录每个字符在模式串中的位置，数组下标可以直接对
 * 应字符的ASCII码值，数组的值为字符在模式串中的位置，没有的记为-1
 */
public class BMMatch {
    /**
     * BM算法匹配，找不到return -1
     *
     * @param main
     * @param pattern
     * @return
     */
    public static int bad(char[] main, char[] pattern) {
        int n = main.length;
        int m = pattern.length;
        int bc[] = new int[256];
        genBC(pattern, m, bc);
        //对齐的第一个字符
        int i = 0;
        while (i <= n - m) {
            //坏字符在模式串中的下标
            int j;
            for (j = m - 1; j >= 0; j--) {
                if (main[i + j] != pattern[j]) {
                    break;
                }
            }
            if (j < 0) {
                return i;//主串的位置
            }
            //滑动位（si-xi）
            i = i + (j - bc[(int) main[i + j]]);

        }
        return -1;
    }

    /**
     * 模式串字典
     *
     * @param b
     * @param m
     * @param dc
     */
    private static void genBC(char[] b, int m, int[] dc) {
        //初始化字典
        for (int i = 0; i < 256; i++) {
            //初始值都是没有
            dc[i] = -1;
        }
        //将模式串中的字符写入字典中
        for (int i = 0; i < m; i++) {
            int asc = (int) b[i];
            /**
             * a b d a
             * 0 1 2 3  i
             *
             * dc:
             * -1 -1 -1 .... 3  1  -1 2
             * 0   1  2  ...97 98 99 100 ...  asc
             *               a  b  c d
             */
            //asc是下标，i是模式串中的位置
            dc[asc] = i;
        }
    }

    public static void main(String[] args) {
        String s1="abcabdcabc";
        String s2="cabc";
        System.out.println(bad(s1.toCharArray(),s2.toCharArray()));
    }
}
